题目|思路_LeetCode刷题笔记数据结构day2

篇首语：本文由编程笔记#小编为大家整理，主要介绍了LeetCode刷题笔记-数据结构-day2相关的知识，希望对你有一定的参考价值。

文章目录

• LeetCode刷题笔记-数据结构-day2
• • 75.颜色分类
  • • 1.题目描述
    • 2.解题思路
    • 3.代码
    
    
  • 56.合并区间
  • • 1.题目描述
    • 2.解题思路
    • 3.代码
    
    
  • 706.设计哈希映射
  • • 1.题目描述
    • 2.解题思路
    • 3.代码
    
    
  
  

75.颜色分类

1.题目描述

原题链接&＃xff1a;75. 颜色分类

2.解题思路

算法&＃xff1a;双指针算法

题目要求&＃xff1a;不使用内置排序函数。使用常数空间

具体思路&＃xff1a;

1. 假设数组长度为n。使用三个指针 i、j、k&＃xff0c;初始化i&＃61;0、j&＃61;n-1、k&＃61;0

2. 从k开始遍历&＃xff0c;分三种情况&＃xff1a;

   
   

   1. 如果a[k]&＃61;&＃61;0。swap(a[i&＃43;&＃43;],a[k&＃43;&＃43;]);

      这里a[i]一定是不等于2的。因为如果等于2&＃xff0c;会执行第二种操作&＃xff0c;所以不可能为2。

      所以a[i]&＃61;&＃61;1&＃xff0c;a[k]&＃61;&＃61;0&＃xff0c;因此交换后&＃xff0c;i和k都可以往后移一位

   2. 如果a[k]&＃61;&＃61;2。 swap(a[j--],a[k]);

      因为这里a[j]的值可能也是2&＃xff0c;所有这里k交换后不能往后移。

   3. 如果a[k]&＃61;&＃61;1。k&＃43;&＃43;;

3.代码

class Solution
public:
void sortColors(vector<int>& a)
int n&＃61;a.size();
int i&＃61;0,j&＃61;n-1,k&＃61;0;
while(k<&＃61;j)
if(a[k]&＃61;&＃61;0) swap(a[i&＃43;&＃43;],a[k&＃43;&＃43;]);
else if(a[k]&＃61;&＃61;2) swap(a[j--],a[k]);
else k&＃43;&＃43;;


;


56.合并区间

1.题目描述

原题链接&＃xff1a;56. 合并区间

2.解题思路

直接套用区间合并的模板即可&＃xff1a;

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)

vector<PII> res;
sort(segs.begin(), segs.end());
int st &＃61; -2e9, ed &＃61; -2e9;
for (auto seg : segs)
if (ed < seg.first)

if (st !&＃61; -2e9) res.push_back(st, ed);
st &＃61; seg.first, ed &＃61; seg.second;

else ed &＃61; max(ed, seg.second);
if (st !&＃61; -2e9) res.push_back(st, ed);
segs &＃61; res;



3.代码

class Solution
public:
vector<vector<int>> merge(vector<vector<int>>& v)
vector<vector<int>> res;
sort(v.begin(),v.end());
int st&＃61;-2e9,ed&＃61;-2e9;
for(auto x:v)
if(ed<x[0])
if(st!&＃61;-2e9) res.push_back(st,ed);
st&＃61;x[0],ed&＃61;x[1];

else ed&＃61;max(x[1],ed);

if(st!&＃61;-2e9) res.push_back(st,ed);
return res;

;


706.设计哈希映射

原题链接&＃xff1a;706. 设计哈希映射

1.题目描述

2.解题思路

题目要求&＃xff1a;不使用任何内建的哈希表库设计一个哈希映射&＃xff08;HashMap&＃xff09;

具体思路&＃xff1a;

哈希表的基本思想都是先开一个大数组&＃xff0c;然后用某种哈希函数将key映射到数组的下标空间。不同算法的区别在于如何处理下标冲突&＃xff0c;即当两个不同的key被映射到同一下标时。我们这里使用拉链法解决冲突。这里的链表我们可以用vector实现。

• 对于put(key, value)操作&＃xff0c;我们先求出key的哈希值&＃xff0c;然后遍历该位置上的链表&＃xff0c;如果链表中包含key&＃xff0c;则更新其对应的value&＃xff1b;如果链表中不包含key&＃xff0c;则直接将&＃xff08;key&＃xff0c;value&＃xff09;插入该链表中。
• 对于get(key)操作&＃xff0c;求出key对应的哈希值后&＃xff0c;遍历该位置上的链表&＃xff0c;如果key在链表中&＃xff0c;则返回其对应的value&＃xff0c;否则返回-1。
• 对于remove(key)&＃xff0c;求出key的哈希值后&＃xff0c;遍历该位置上的链表&＃xff0c;如果key在链表中&＃xff0c;则将其删除。

3.代码

const int N&＃61;1e4&＃43;3;
class MyHashMap
public:
vector<pair<int,int>> h[N];
MyHashMap()

int find(vector<pair<int,int>> &h,int key)
for(int i&＃61;0;i<h.size();i&＃43;&＃43;)
if(h[i].first&＃61;&＃61;key) return i;
return -1;

void put(int key, int value)
int t&＃61;key%N;
int k&＃61;find(h[t],key);
if(k&＃61;&＃61;-1) h[t].push_back(key,value);
else h[t][k].second&＃61;value;


int get(int key)
int t&＃61;key%N;
int k&＃61;find(h[t],key);
if(k&＃61;&＃61;-1) return -1;
return h[t][k].second;


void remove(int key)
int t&＃61;key%N;
int k&＃61;find(h[t],key);
if(k!&＃61;-1) h[t].erase(h[t].begin()&＃43;k);

;